package 构造二叉树;

import java.util.Arrays;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 从前序与中序遍历序列构造二叉树
 * @date 2022/11/6 13:40
 */
public class Demo105 {
    public static void main(String[] args) {
        int[] inorder = {9,3,15,20,7};
        int[] preorder = {3,9,20,15,7};
        TreeNode treeNode = buildTree(preorder, inorder);
        System.out.println(treeNode);

    }
    //1.递归条件
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        //输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
        //输出: [3,9,20,null,null,15,7]


        //递归终止条件
        if(preorder.length==0){
            return null;
        }
        //找到root节点
        TreeNode root=new TreeNode(preorder[0]);
        //在中序数组中找到根节点
        int index=0;
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i]== root.val){
                break;
            }
            index++;
        }
        //分割数组
        int[] inorderPre= Arrays.copyOfRange(inorder,0,index);
        int[] inorderInorder= Arrays.copyOfRange(inorder,index+1,inorder.length);
        int[] preorderPre= Arrays.copyOfRange(preorder,1,1+inorderPre.length);
        int[] preorderInorder= Arrays.copyOfRange(preorder,1+inorderPre.length,inorder.length);
        root.left=buildTree(preorderPre,inorderPre);
        root.right=buildTree(preorderInorder,inorderInorder);
        return root;
    }

    //Definition for a binary tree node.
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
